package com.leetcode.algorithm.y22.m07.w4;

import com.leetcode.algorithm.common.ListNode;

/**
 * 24. 两两交换链表中的节点
 * 
 * https://leetcode.cn/problems/swap-nodes-in-pairs/
 * 
 * @author jie.deng
 *
 */
class Question0024Solution01 {
	
	public ListNode swapPairs(ListNode head) {
		ListNode sentinel = new ListNode();
		sentinel.next = head;

		ListNode prev = sentinel;
		ListNode next = null;

		while (prev != null && prev.next != null) {
			ListNode left = prev.next;
			if (left != null && left.next != null) {
				ListNode right = left.next;
				next = right.next;
				// 需要交换left和right
				prev.next = right;
				right.next = left;
				left.next = next;
				// 更新prev
				prev = left;
			} else {
				break;
			}
		}

		return sentinel.next;
	}
    
}